
%% 
%% 
%% 
%% by Karthik Ganesan Pillai
%%



% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/

\documentclass[conference]{IEEEtran}
%\documentclass[10pt, twocolumn, final, conference]{IEE}
% Add the compsoc option for Computer Society conferences.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}







% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.




\usepackage{multirow}

% *** CITATION PACKAGES ***
%
%\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{epsfig}
\ifCLASSINFOpdf
   %\usepackage[pdftex]{graphicxsp}
%\usepackage{graphicxsp}
  % declare the path(s) where your graphic files are
  %\graphicspath{{C:\\Documents and Settings\\k.ganesanpillai\\My Documents\\NetBeansProjects\\Analysis  Folder\\Paper}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
 %\DeclareGraphicsExtensions{.pdf,.jpeg,.png,.eps,.bmp}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
 %  \graphicspath{{{C:\\Documents and Settings\\k.ganesanpillai\\My Documents\\NetBeansProjects\\Analysis  Folder\\Paper}{C:\\Documents and Settings\\k.ganesanpillai\\My Documents\\NetBeansProjects\\Analysis  %Folder\\Paper}}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
 %  \DeclareGraphicsExtensions{.eps,.bmp}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage{algorithmic}
\usepackage{algorithm}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/





% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.



%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.





% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{Pyramid-Technique}


% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{\IEEEauthorblockN{Karthik Ganesan Pillai}
\IEEEauthorblockA{Department of Computer Science\\
Montana State University\\
EPS 357, PO Box 173880\\
Bozeman, MT 59717-3880\\
k.ganesanpillai@cs.montana.edu\\
}
\and
\IEEEauthorblockN{ Josh Strissel}
\IEEEauthorblockA{Department of Computer Science\\
Montana State University\\
EPS 357, PO Box 173880\\
Bozeman, MT 59717-3880\\
joshua.strissel@gmail.com\\
}
\and
\IEEEauthorblockN{Shaun Ross}
\IEEEauthorblockA{Department of Computer Science\\
Montana State University\\
EPS 357, PO Box 173880\\
Bozeman, MT 59717-3880\\
sross44@gmail.com\\
}

}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass





% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle


\begin{abstract}
%\boldmath
In this paper, Pyramid-Technique, a high dimensional indexing method
is analyzed for different high dimensional data spaces. In Pyramid-Technique,
high dimensional data space is first divided into 2d pyramids sharing
the center point of the space as a top. In the next step, each pyramid
is sliced parallel to the basis of the pyramid at several points.
By partitioning the high dimensional data space in this way, d-dimensional
space is mapped to a 1-dimensional space. Pyramid-Technique is compared
with other extended variations of Pyramid-Technique and sequential
scan. In extended variations of Pyramid-Technique, center point of
the data space chosen is from actual mediods or approximate mediods
of the high dimensional data space. By choosing the center point of
data space in this way, partitions of pyramids will be more evenly
spread out for different data distributions.
\end{abstract}
\vspace{3mm}
\begin{IEEEkeywords}
Backpropagation, machine learning, neural networks, particle swarm optimization, swarm intelligence
\end{IEEEkeywords}

% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the conference you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals/conferences frown on
% math in the anyway.

% no keywords




% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}
% no \IEEEPARstart
Pyramid-Technique was introduced by Stephan Berchtold et al. \cite{1}
in 1998, to address the problem creating efficient index-structures
for high dimensional data spaces. With the increasing usage of variety
of databases applications such as datawarehousing and GIS, and increasing
multimedia applications require the support of query processing on
large amounts of high dimensional data. Development of Pyramid-Technique
was motivated by drawbacks of other multidimensional indexing techniques.
Multidimensional indexing techniques suffer from performing badly
on high dimensional data and also these techniques are restricted
with respect to data space partitioning strategies. Moreover, multidimensional
indexing techniques suffer from high costs for insert and delete operations
and a poor support of concurrency control and recovery \cite{1}.

Pyramid-Technique is based on a partitioning strategy that is optimized
for high dimensional data. In the first step, high dimensional data
space is divided into 2d pyramids with center point of the data space
as the top of all the pyramids. Next, each pyramid is sliced at various
points parallel to the basis of the pyramid, thus forming data pages.
It is analytically shown in \cite{1}, that for uniform data distribution
and hypercubed shaped queries, the Pyramid-Technique does not gets
affected by {}``curse of dimensionality'' i.e., the performance
of Pyramid-Technique does not deterioate when going to higher dimension.
Also, since Pyramid-Technique maps d-dimensional space to 1-dimensional
space, a B+-tree {[}\cite{2,3}{]} can be used to store data items
and make use of nice properties of B+-tree, such as fast insert, update
and delete operations. And thus Pyramid-Technique can be easily implemented
on top of an existing DBMS \cite{1}.


\section{Related Work}
I am Karthik with value $pow(1,2)$


\section{Pyramid Technique}

The Pyramid-Technique divides the high dimensional data space to 2d
pyramids that share the center point of the data space as top of each
pyramid and (d-1) dimensional surfaces of data space as their base.
A point in the data space is associated to a unique pyramid and the
point also has a non unique height within that pyramid it is associated
to.  And this association of point to a pyramid is called pyramid value of a point in the data space.
Any order preserving one dimensional index structures can be used to index pyramid values.  Figure \ref{fig:1}
represents insert and range query processing. For both insert and range query processing, d-dimensional input is transformed
into 1-dimensional value which can be processed by the B+-tree. In the leaf nodes of B+-tree,
d-dimensional point value and 1-dimensional key value are stored, thus inverse transformaiton is not neccessary. In the next section, data space
partitioing will be explained in detail.

\begin{figure}[b]
\begin{centering}
\includegraphics[scale=.30]{operationsonindex}
\par\end{centering}
\caption{\label{fig:1}Operations on Indexes, adapted from \cite{1}}
\end{figure}




Calculating the pyramid number and height within that pyramid
for each point is given in algorithm \ref{alg:PV}.
\subsection{Data Space Partitioning:}
Partition of data space in the Pyramid-Technique follows two steps. In the first step, the d-dimensional
data space is divided into $2d$ pyramids, with center point of data space as top of each pyramid and $(d-1)$ dimensional surface
as base of each pyramid. In the second step, each of the pyramid is divided into multiple partitions, and each partition correspond to 
one data page of the B+-tree. Figure \ref{fig:2} (left), shows the partitioning of $2$-dimensional data space into $4$ pyramids which all
have the center point of data space as top and one edge of the data space as base. Figure \ref{fig:2} (right), shows the partitions within each pyramid, parallel
to the base line. 

\begin{figure}[b]
\begin{centering}
\includegraphics[scale=.30]{dataspacepartition}
\par\end{centering}
\caption{\label{fig:2}Partition of data space into pyramids,  adapted from \cite{1}}
\end{figure}

\subsection{Calculation of Pyramid value of a point and index creation}
Pyramid value of a point ($pv_{v}$), is the summation of pyramid number and height of the point within that pyramid. Calculation
of pyramid number and height of a point is shown in algorithm \ref{alg:PV}. Figure \ref{fig:3}, shows the number assigned to pyramids for data
points in those pyramids and Figure \ref{fig:4}, shows the height of a point within it's pyramid. Using the $pv_{v}$ as a key, the $d$-dimensional point is inserted in B+tree in the according data page of the B+-tree. 



\begin{figure}[b]
\begin{centering}
\includegraphics[scale=.30]{propertiesofpyramids}
\par\end{centering}
\caption{\label{fig:3}Properties Of Pyramids,  adapted from \cite{1}}
\end{figure}

\begin{figure}[b]
\begin{centering}
\includegraphics[scale=.30]{heightofpoint}
\par\end{centering}
\caption{\label{fig:4}Height of a point within it's pyramid,  adapted from \cite{1}}
\end{figure}





\begin{algorithm}[h]
\begin{algorithmic}
\caption{\label{alg:PV}To calculate pyramid value of a point $v$, adapted from \cite{1}.}
\STATE PyramidValue(Point $v$)
\STATE $d_{max}=0$
\STATE $height=|0.5-v_0|$
\FOR{$j=1 \to D-1$}
\IF {$height<|0.5-v_j|$}
\STATE {$d_{max}=j$}
\STATE $height=|0.5-v_j|$
\ENDIF
\ENDFOR

\IF {$values[d_{max}]<0.5$}
\STATE {$i=d_{max}$}
\ELSE
\STATE {$i=d_{max}+D$}
\ENDIF
\STATE{$pv_{v}=i+height$}
\RETURN {$pv_{v}$}

\end{algorithmic}
\end{algorithm}
\section{Query Processing}
Point queries, range queries and KNN queries are discussed in this section. First, lets start with point queries which are defined
as "Given a query point q, decide whether q is in the database". This problem can be solved, by first finding the pyramid value $pv_{q}$ of query point 
q and querying the B+-tree using $pv_{q}$. Thus, d-dimensional results are obtained sharing the pyramid value $pv_{q}$. From this result, we scan and determine
whether the result contains q and output the result.

Second for range queries, which are defined as "Given a d-dimensional interval $[q_{0_{min}},  q_{0_{max}}],...,[q_{d-1_{min}}, q_{d-1_{max}}]$,
determine the points in the database which are inside the range". Range query processing using the Pyramid-Technique is a complex operation. A query rectangle might intersect several pyramids, 
and computation of the area of interval is not trivial. This computation of the area is a two step process. First, we need determine which pyramid intersects with the query rectanlge, and second we
need to determing ranges inside the pyramids. To determing range inside a pyramid ($h_{v}$ between two values) for all objects is an one dimensional indexing problem. From Figure \ref{fig:5},
it can be seen that some candidates are hits, and others are false hits. Then, a simple point-in-rectangle is performed in refinement step.

Procedure to find pyramid intersection and ranges within the pyramid for range queries is given in  algorithm \ref{alg:QR} and it uses equations 1-6.

\begin{figure}[b]
\begin{centering}
\includegraphics[scale=.30]{transformationofrangequeries}
\par\end{centering}
\caption{\label{fig:5}Transformation of range queries,  adapted from \cite{1}}
\end{figure}



\begin{figure*}
\begin{centering}

\begin{equation}\label{eq:1}
intersect=
\begin{cases}
true & \text{if $k=D$ }\\
false & \text{if $k!=D$ }\\
\end{cases}
\end{equation}
where $k$ is obtained from equation \ref{eq:2}
\begin{equation}\label{eq:2}
k = 
\begin{cases}
\forall j, 0 \leq j<D, \hat q_{i_{min}} \leq -MIN( \hat q_{j}): & \text{if $i<D$ }\\
\forall j, 0 \leq j<D, \hat q_{{i-D}_{min}} \geq -MIN( \hat q_{j}): & \text{if $D-1<i$}\\
\end{cases}
\end{equation}

\begin{equation}\label{eq:3}
h_{low},  h_{high}=
\begin{cases}
0, MAX(\hat q_{i}) & \text{if $ \forall j,  0 \leq j<D:(\hat q_{j_{min}} \leq 0 \leq  \hat q_{j_{max}} ) $ }\\
max_{0 \leq j<D}:(\bar q_{j})(*), MAX(\hat q_{i}) & \text{if $Otherwise$ }\\
\end{cases}
\end{equation}

\begin{equation}\label{eq:4}
\bar q_{j}=
\begin{cases}
MIN(q_{j}) & \text{if MIN$(q_{j}) > $MIN$(q_{i})$ }\\
MIN(q_{i}) & \text{if $Otherwise$ }\\
\end{cases}
\end{equation}


\begin{equation}\label{eq:5}
MIN(r)=
\begin{cases}
0 & \text{if $r_{min} \leq 0 \leq r_{max}$ }\\
min(|r_{min}|,|r_{max}|) & \text{if $Otherwise$ }\\
\end{cases}
\end{equation}

\begin{equation}\label{eq:6}
MAX(r)=max(|r_{min}|,|r_{max}|)
\end{equation}

\par\end{centering}
\caption{\label{fig:6}Equations to find intersection of pyramid and ranges within pyramid and query rectangle,  adapted from \cite{1}}
\end{figure*}

\begin{algorithm}[t]
\begin{algorithmic}
\caption{\label{alg:QR}To process query $[\hat q_{0_{min}}, \hat q_{0_{max}}],...,[\hat q_{d-1_{min}}, \hat q_{d-1_{max}}]$, adapted from \cite{1}.}
\STATE QuerySearch($qr[D][2]$)
\STATE //Initiaze variables
\STATE $subquery[D][2]$
\STATE $qw[D][2]$

\FOR{$i=0 \to D-1$}
\STATE $subquery[i][0] = qr[i][0] - 0.5$
\STATE $subquery[i][1] = qr[i][1] - 0.5$
\ENDFOR

\FOR{$i=0 \to (2D)-1$}
\FOR{$j=0 \to D-1$}
\STATE $qw[j][0]=subquery[j][0]$
\STATE $qw[j][1]=subquery[j][1]$
\ENDFOR

\STATE // Use Equation \ref{eq:1} to find whether pyramid i intersects with
  $qw[i]$
\IF {intersect} 
\IF {$(i<D) \wedge (qw[i][1]>0)$}
\STATE $qw[i][1]=0$
\ENDIF
\STATE Use Equation \ref{eq:3} to find $h_{low}$ and $h_{high}$ for $qw[i]$
\ENDIF
\ENDFOR



\end{algorithmic}
\end{algorithm}


Third, for KNN query which are defined as "Given a set $S$ of n $d$-dimensional data points and a query  point q, the k-nearest neighbor (KNN) search is to 
find subset $S' \subseteq S$ of $k \leq n$ data points such that for any data point $u \in S'$ and $S-S'$, $dist(u,q) \leq dist(v,q)$. 


\begin{algorithm}[t]
\begin{algorithmic}
\caption{\label{alg:KNN}TThe decreasing radius Pyramid KNN search algorithm, adapted from \cite{4}.}
\STATE PyramidKNN($Point \textrm {   } q, int \textrm {   } k$)
\STATE $A  \leftarrow emptyset$
\STATE $i  \leftarrow pyramid  number of the pyramid q is in $
\STATE $node  \leftarrow LocateLeft(T,q)$
\STATE $SearchLeft(node,A,q,i)$
\STATE $SearchRight(node,A,q,i+0.5)$
\STATE $D_{max}  \leftarrow D(A_{0},q)$
\STATE $Generate\textrm {   } W\textrm {   }  centered\textrm {   } at\textrm {   } q\textrm {   } with\textrm {   } \bigtriangleup \leftarrow 2D_{max}$
\FOR{$j=0 \to 2D-1$}
\IF {$(j \neq i) \wedge (W \textrm {   } intersects\textrm {   }  pyramid\textrm {   }  j) $}
\STATE Query Search
\ENDIF
\ENDFOR

\end{algorithmic}
\end{algorithm}




\section{Extended Pyramid-Technique}
The data partitioning strategy of the Pyramid-Technique supports uniform data distribution very well. For clustered data (see Figure \ref{fig:6} left)
only a few pyramids will containt most of the data while other pyramids are nearly empty. Patitioning this data space will result in suboptimal space partition as shown in Figure \ref{fig:6} (middle).
A better partitioning approach is shown in Figure \ref{fig:6} (right). 

In extended Pyramid-Technique, the basic idea is to transform the data space such that the data cluster is located in the center point (0.5,...,0.5) of space. Thus the data space is mapped to the canonical
data space $[0,1]^d$ such that the d-dimensional median of the data space is mapped to the center point. The transformation is applied only to determine the pyramid value os points and query rectangles, 
and hence inverse transformation is not neccessary.

Computation of median for d-dimensional space is time consuming and hard. Hence two different kinds of approximate median finding appraoches are explored. The first approximate median finding algorithm
is based on histogram. In this approach, a histogram is maintained for each dimension to keep track of median in each dimension. 

In the second approach, median for each dimension is obtained by using an algorithm given in \cite{5}. The d-dimensional median is then approximated by the combination of the d-dimensional medians.

This d-dimensional approximate median may lie outside the convex hull of the data cluster. The computation of median can be done dynamically in cased of dynamic insertions or once in case of bulk load of the index.

In \cite{1}, given the d-dimensional median mp of the data set,  a set of d functions $t_{i}$ are defined, $0 \leq i < (d-1)$ transforming the given data space in dimension i such that the following conditions hold:

\begin{itemize}
\item{$t_{i}(0)=0$}
\item{$t_{i}(1)=1$}
\item{$t_{i}(mp_{i})=0.5$}
\item{$t_{i}:[0,1] \rightarrow [0,1]$}
\end{itemize}

The first three condition ensure that the transformed data space still has an extension of $[0..1]^d$ (1 and 2) and that the median of the data becomes center point of the data space (3). The last condition (4), assures that each
point in the original data space is mapped to a point inside the canonical data space. The resulting functions $t_{i}$  can be chosen as an exponential function such that: $t_{i}(x)=x^r$. Conditions 1,2, and 4 are satisfied by $x^r$,
$r \geq 0, 0 \leq x \leq 1$.  To determine $r$,  condition 3 has to be satisfied.  Thus, $r=1/log_{2}(mp_{i})$ and 

\begin{equation}\label{eq:6}
t_{i}(x)=x^{-(1/log_{2}(mp_{i}))}
\end{equation}

To insert a point $v$ into an index, transform $v$ into a point $v_{i}'=t_{i}(v_{i})$ and determine the pyramid value $pv_{v'}$. Using $pv_{v'}$, point $v$ is inserted into B+-tree. To process a query, first transform the query rectangle $q$ into a query
rectanlge $q'$ such that $q'_{i_{min}}=t_{i}(q_{i_{min}})$ and $q'_{i_{max}}=t_{i}(q_{i_{max}})$. Next algorithms discussed in earlier sections are used to determine intersection of pyramids and ranges within pyramids to find the points in the query
rectangle. Finally refinement of points is performed to filter out false hits.


\begin{figure}[b]
\begin{centering}
\includegraphics[scale=.30]{clustereddata}
\par\end{centering}
\caption{\label{fig:6}Transformation of range queries,  adapted from \cite{1}}
\end{figure}





\section{Experimental Setup}

\section{Experimental Results}

\section{Discussion}

\section{Conclusions and Future Work}


\bibliographystyle{IEEEtran}
\nocite{*}
\bibliography{PyramidReference}








\end{document}


